#include"Thompson.tab.h"
// #include<iostream>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include"dfanode.h"
extern FILE* yyin;
std::vector<RegularExpressionNode*> root_exps;
std::map<NFA_node*,int>vsd;
void NFA_dfs(NFA_node* cur,NFA_node* end){
    vsd[cur]=vsd.size()+1;
    for(auto edgs:cur->edges){
        for(auto dst:(edgs.second)){
            if(vsd.find(dst)==vsd.end())
                NFA_dfs(dst,end);
            std::cout<<vsd[cur]<<" "<<(char)edgs.first<<" "<<vsd[dst];
            if(dst==end){
                std::cout<<"(end node)";
            }
            std::cout<<"\n";
        }
    }
}
std::set<NFA_node*>Delta(std::set<NFA_node*>src,int ch){
    std::set<NFA_node*>res;
    for(auto node:src){
        for(auto edgs:node->edges){
            if(edgs.first==ch){
                for(auto dst:edgs.second){
                    res.insert(dst);
                }
            }
        }
    }
    return res;
}
std::set<NFA_node*>eps_closure(std::set<NFA_node*>src){
    std::stack<NFA_node*>st;
    std::set<NFA_node*>res;
    for(auto node:src){
        st.emplace(node);
        res.insert(node);
    }
    while(!st.empty()){
        auto node = st.top();
        st.pop();
        for(auto edgs:node->edges){
            if(edgs.first==0){
                for(auto dst:edgs.second){
                    if(res.count(dst)==0){
                        res.insert(dst);
                        st.emplace(dst);
                    }
                }
            }
        }
    }
    return res;
}
std::map<std::set<NFA_node*>,DFA_node*>DFA_map;
DFA_node*ConstructDFA(NFA_node*begin,NFA_node*end){
    std::set<NFA_node*>begin_states;
    begin_states.insert(begin);
    DFA_node* ret_root;

    std::set<NFA_node*>begin_closure=eps_closure(begin_states);
    ret_root=DFA_map[begin_closure]=new DFA_node(begin_closure.count(end)!=0);
    std::queue<std::set<NFA_node*> >sets_queue;
    sets_queue.push(begin_closure);
    while(!sets_queue.empty()){
        std::set<NFA_node*>cur=sets_queue.front();
        sets_queue.pop();
        for(int i=1;i<=127;i++){
            std::set<NFA_node*>next=eps_closure(Delta(cur,i));
            if(next.empty())continue;
            if(DFA_map[next]==0){
                DFA_map[next]=new DFA_node(next.count(end)!=0);
                sets_queue.push(next);
            }
            if(DFA_map[cur]->edges[i]!=NULL){
                std::cout<<"??????\n";
            }
            DFA_map[cur]->edges[i]=DFA_map[next];
        }
    }
    return ret_root;
}
void Step_DFA(DFA_node*dfa_root,char*str){
    DFA_node*dfa_cur=dfa_root;
    char* cur_str;
    int i=0;
    for(cur_str=str;*cur_str;cur_str++,i++){
        dfa_cur=dfa_cur->edges[*cur_str];
        if(dfa_cur==NULL){
            printf("Illegal at %d\n",i);
            printf("Matching aborted\n");
            break;
        }
        if(dfa_cur->ended()){
            printf("Matched at %d\n",i);
        }
    }
    if(!(dfa_cur->ended())){
        printf("Match Failed\n");
    }else printf("Match Success\n");
}
int next_group=3;
std::map<DFA_node*,int>DFA_group,DFA_vsd,DFA_no;
std::vector<std::set<DFA_node*>* >pi;
void DFA_refresh_group(){
    DFA_group.clear();
    for(int i=0;i<pi.size();i++){
        for(auto node:*(pi[i])){
            DFA_group[node]=i+1;
        }
    }
}
void DFA_init_group_DFS(DFA_node*dfa_cur){
    DFA_vsd[dfa_cur]=1;
    if(dfa_cur->ended())pi[0]->insert(dfa_cur);
    else pi[1]->insert(dfa_cur);
    for(auto outEdg:dfa_cur->edges){
        if(DFA_vsd[outEdg.second]==0){
            DFA_init_group_DFS(outEdg.second);
        }
    }
}
void DFA_init_group(DFA_node*dfaRoot){
    pi.clear();
    pi.push_back(new std::set<DFA_node*>);
    pi.push_back(new std::set<DFA_node*>);
    DFA_init_group_DFS(dfaRoot);
    DFA_refresh_group();
}
bool split_pi(){
    bool changed=false;
    std::vector<std::set<DFA_node*>*>splited_pi;
    for(auto Set:pi){
        std::vector<std::set<DFA_node*>* >new_pi_part;
        for(auto node:*Set){
            int found=0;
            for(auto new_Set_ele:new_pi_part){
                DFA_node* represent = *(new_Set_ele->begin());
                int can_join=1;
                for(int i=1;i<=127;i++){
                    if( DFA_group[represent->edges[i]]
                        !=
                        DFA_group[node->edges[i]]){
                        can_join=0;
                        break;
                    }
                }

                if(can_join){
                    new_Set_ele->insert(node);
                    found=1;
                    break;
                }
            }
            if(found==0){
                std::set<DFA_node*>*new_pi=new std::set<DFA_node*>();
                new_pi->insert(node);
                new_pi_part.push_back(new_pi);
            }
        }
        if(new_pi_part.size()!=1)changed=true;
        splited_pi.insert(splited_pi.end(),new_pi_part.begin(),new_pi_part.end());
    }
    for(auto oldSet:pi){
        delete oldSet;
    }
    pi.clear();
    pi.insert(pi.end(),splited_pi.begin(),splited_pi.end());
    DFA_refresh_group();
    return changed;
}
DFA_node* DFA_Minimize(DFA_node*dfaRoot){
    DFA_init_group(dfaRoot);
    while(split_pi()){}
    std::vector<DFA_node*>minimized_states;
    DFA_node* minimized_root=NULL;
    for(int i=0;i<pi.size();i++){
        DFA_node* represent = *(pi[i]->begin());
        minimized_states.push_back(new DFA_node(represent->ended()));
        // minimized_states[0] -- DFA_group[]==1 -- pi[0]
        if(pi[i]->count(dfaRoot)!=0){
            minimized_root=minimized_states[i];
            std::cout<<i<<"\n";
        }
    }
    for(int i=0;i<pi.size();i++){
        DFA_node* represent = *(pi[i]->begin());
        for(auto edge:represent->edges){
            if(edge.second==NULL)continue;
            // std::cout<<i+1<<" "<<(char)edge.first<<DFA_group[edge.second]<<"\n";
            minimized_states[i]->edges[edge.first]=
            minimized_states[DFA_group[edge.second]-1];
        }
    }
    
    return minimized_root;
}
void DFA_DFS_preview(DFA_node*dfa_cur){
    DFA_no[dfa_cur]=DFA_no.size()+1;
    // std::cout<<DFA_no[dfa_cur]<<"\n";
    for(auto outEdg:dfa_cur->edges){
        // std::cout<<"11\n";
        if(DFA_no.find(outEdg.second)==DFA_no.end()){
            // std::cout<<outEdg.second<<"\n";
            DFA_DFS_preview(outEdg.second);
        }
        std::cout<<DFA_no[dfa_cur]<<" "<<(char)outEdg.first<<" "<<DFA_no[outEdg.second];
        if(outEdg.second->ended()){
            std::cout<<"(end)";
        }
        std::cout<<"\n";
    }
}
char test_str[80];
int main(){
    FILE*f=fopen("in.txt","r");
    freopen("out.txt","w",stdout);
    yyin=f;
    yyparse();
    NFA_node* begin;
    NFA_node* end;
    for(auto root_exp : root_exps){
        printf("AST:\n");
        root_exp->printAST(0,std::cout);

        root_exp->ConstructNFA(begin,end);
        printf("Constructed NFA\n");
        vsd.clear();
        NFA_dfs(begin,end);

        DFA_node* DFA_begin=ConstructDFA(begin,end);
        printf("Constructed DFA\n");
        DFA_no.clear();
        DFA_DFS_preview(DFA_begin);

        DFA_node* DFA_mini_root=DFA_Minimize(DFA_begin);
        printf("Minimized DFA\n");
        DFA_no.clear();
        DFA_DFS_preview(DFA_mini_root);

        printf("Input str to be matched:\n");
        scanf("%s",test_str);
        printf("%s\n",test_str);
        Step_DFA(DFA_begin,test_str);
    }
    fclose(f);
    return 0;
}